package com.cheung.leetcode.dp;

import org.junit.jupiter.api.Test;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.dp
 * @Author :  cheungming
 * @CreateTime : 2024-06-13 14:58:02
 * @Description : 最后一块 石头的重量 II
 * @Version : 1.0
 */
public class Code1094Test {

    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        // 背包问题
        int target = sum / 2;
        // dp[i] 表示背包容量为 i 时，最大可以装的重量，背包容量可以为0到sum/2
        int[] dp = new int[target + 1];
        // 遍历物品,对于每个物品,遍历背包,更新dp[j]
        for (int stone : stones) {
            // 倒序遍历, 从大到小遍历
            for (int j = target; j >= stone; j--) {
                // dp[j]表示stone不装入背包时的最大重量,dp[j-stone]表示stone装入背包时的最大重量，取两者的最大值
                dp[j] = Math.max(dp[j], dp[j - stone] + stone);
            }
        }
        return sum - dp[target] * 2;
    }

    @Test
    public void test1() {
        int[] stones = {2, 7, 4, 1, 8, 1};
        assert lastStoneWeightII(stones) == 1;
    }

    @Test
    public void test2() {
        int[] stones = {31, 26, 33, 21, 40};
        assert lastStoneWeightII(stones) == 5;
    }
}

